Paper 2022/1223

Efficient Proofs of Software Exploitability for Real-world Processors

Matthew Green, Johns Hopkins University
Mathias Hall-Andersen, Aarhus University
Eric Hennenfent, Trail of Bits
Gabriel Kaptchuk, Boston University
Benjamin Perez, Trail of Bits
Gijs Van Laer, Johns Hopkins University
Abstract

We consider the problem of proving in zero-knowledge the existence of vulnerabilities in executables compiled to run on real-world processors. We demonstrate that it is practical to prove knowledge of real exploits for real-world processor architectures without the need for source code and without limiting our consideration to narrow vulnerability classes. To achieve this, we devise a novel circuit compiler and a toolchain that produces highly optimized, non-interactive zero-knowledge proofs for programs executed on the MSP430, an ISA commonly used in embedded hardware. Our toolchain employs a highly optimized circuit compiler and a number of novel optimizations to construct efficient proofs for program binaries. To demonstrate the capability of our system, we test our toolchain by constructing proofs for challenges in the Microcorruption capture the flag exercises.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. PoPETs
Keywords
zero-knowledge proof NIZK Reverie exploits real-world processors MSP430 KKW
Contact author(s)
mgreen @ cs jhu edu
mathias @ hall-andersen dk
eric hennenfent @ trailofbits com
kaptchuk @ bu edu
benperez1227 @ gmail com
gijs vanlaer @ jhu edu
History
2022-09-15: approved
2022-09-15: received
See all versions
Short URL
https://ia.cr/2022/1223
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1223,
      author = {Matthew Green and Mathias Hall-Andersen and Eric Hennenfent and Gabriel Kaptchuk and Benjamin Perez and Gijs Van Laer},
      title = {Efficient Proofs of Software Exploitability for Real-world Processors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1223},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1223}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.